/* 
  递归的本质：
  就是将原问题拆解成更小规模问题，最后在组合成原问题的解
  当然这里需要找到边界条件退出递归过程
*/
/* 
  1 数组求和使用递归实现
*/
// 计算一个数组arr [l, arr.length)的和
var _sum = (arr, l) => {
  if (l === arr.length) {
    return 0;
  }
  return arr[l] + _sum(arr, l + 1);
};
var sum = (arr) => {
  return _sum(arr, 0);
};
console.log(sum([1, 2, 3, 4, 5]));

/* 
  2 删除链表中的元素使用递归实现
  思路：链表其实可以拆解看成是一个head头节点和右边一个数量减一的小链表组成
*/
function ListNode(val, next) {
  if (Array.isArray(val)) {
    // 给定一个数组，创建一个头结点
    this.val = val[0];
    let cur = this;
    for (let i = 1; i < val.length; i++) {
      cur.next = new ListNode(val[i]);
      cur = cur.next;
    }
  } else {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
ListNode.prototype.toString = function () {
  let cur = this;
  let res = '';
  while (cur) {
    res += `${cur.val} --> `;
    cur = cur.next;
  }
  return res;
};
// 删除以head为头结点的链表中的所有val值的节点，并返回删除后的头结点
const generateDeep = (index) => {
  let res = '';
  for (let i = 0; i < index; i++) {
    res += '--';
  }
  return res;
};
var removeElements = function (head, val, deep) {
  const deepStr = generateDeep(deep);
  console.log(deepStr);
  if (!head) {
    console.log(deepStr);
    return head;
  }
  head.next = removeElements(head.next, val, deep + 1);
  console.log(deepStr, head.next && head.next.toString());
  return head.val === val ? head.next : head;
};

const head = new ListNode([1, 2, 3, 4, 5]);
removeElements(head, 4, 0);
